package org.shj.algorithm.string;

/**
 * 有红白蓝三种不同颜色的小球，乱序排列在一块，请重新排列小球，使得相同颜色的小球在一起。
 * 此问题也称为荷兰国旗问题。
 * 问题转化： 有一个数组 A[N], 其中只有 0, 1, 2 三种元素。使用算法重新排列，使其顺序为：
 *   00...011...122...2
 * 算法并不难，只是记录一步一步改进的思路
 *
 * @author Shen Huang Jian
 * @date 2019/4/30
 */
public class ThreeColorBall {
    public static void main(String[] args){
        int[] array = new int []{2, 2, 1, 0, 0, 1, 2};
        method1(array);
    }

    /**
     * 定义三个指针，初始值 begin=current=0, end=最后一位
     * 1. 若 A[current] = 2, 则 swap[current, end], 然后 end--， current 不变
     * 2. 若 A[current] = 1, 则 current++， begin 和 end 不变
     * 3. 若 A[current] = 0, 则：
     *    3.1 若 begin == current，则 begin++ 并且 current++
     *    3.2 否则， swap[begin, current], begin++, current 不变
     *
     * @param array
     */
    private static void method1(int[] array){
        int begin = 0;
        int current = 0;
        int end = array.length - 1;

        while(current <= end){
            if(array[current] == 2){
                swap(array, current, end);
                end--;
            }else if (array[current] == 1){
                current++;
            }else{
                if(begin == current){
                    begin++;
                    current++;
                }else{
                    swap(array, begin, current);
                    begin++;
                }
            }
        }

        print(array);
    }

    /**
     * 对 method1 略作优化
     * 根据 method1 中的结论，可以得出在 [begin, current)  这个区间内，肯定没有 2
     * 因此 A[begin] 要么是 0，要么是 1
     * 若 begin != current ，则必有 A[begin] = 1
     * 因此，当 A[current] = 0 时，若 begin != current，则，交换后， A[current]=1,
     * 由上面的第2点得出: current 也可以自增
     * @param array
     */
    private static void method2(int[] array){
        int begin = 0;
        int current = 0;
        int end = array.length - 1;

        while(current <= end){
            if(array[current] == 2){
                swap(array, current, end);
                end--;
            }else if (array[current] == 1){
                current++;
            }else{
                if(begin != current){
                    swap(array, begin, current);

                }
                begin++;
                current++;
            }
        }
    }

    private static void swap(int[] array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    private static void print(int[] array){
        for(int i : array){
            System.out.print(i + ",");
        }
    }
}
